package 中等.动态规划.背包;

/**
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将
 * 这个数组分割成两个子集，使得两个子集的元素和相等
 * <p>
 * 来源：https://leetcode-cn.com/problems/partition-equal-subset-sum/
 */
public class 分割等和子集_416 {

    public static void main(String[] args) {

        int[] nums = {3, 3, 11, 5};
        canPartition(nums);

    }

    /**
     * 1    2   2   1
     * dp[i][j] = 不装：dp[i - 1][j] || 装：dp[i - 1][j - nums[i]]
     * 装了之后可以装满背包或者不装之前背包就已经可以装满=true
     * target容量=3
     * 求：0~i件物品之中是否可以选择某些物品使得装满0,1,2,3,4容量的背包
     * .    0   1   2   3
     * 1    T   T   F   F                  只有一件物品1，需要正好装满背包
     * 2    T   T   T   T当前容量有3，物品是2必须装，装了后容量还剩下1，上一件物品容量为1的背包是否可以装下，dp[0][1]=T
     * 2    T   T   T   T
     * 1    T   T   T   T
     * 容量为0，直接装满背包
     * --------------------------------------------------------
     * 1   5   11  5
     * 解：
     * target=11
     * 装：装了后剩下的容量是否可以被装满，上一件物品的剩下容量
     * 不装：上一件物品是否可以装满背包
     * .    0   1   2   3   4   5   6   7   8   9   10  11
     * 1    T   T   F   F   F   F   F   F   F   F   F   F
     * 5    T   T   F   F   F   T   T   F   F   F   F   F
     * 11   T   T   F   F   F   T   T   F   F   F   F   T
     * 5    T   T   F   F   F   T   T   F   F   F   T   T
     *
     * @param nums
     * @return
     */
    public static boolean canPartition(int[] nums) {
        int totol = 0, maxNum = nums[0];
        for (int num : nums) {
            totol = totol + num;
            maxNum = Math.max(num, maxNum);
        }
        //如果总数是奇数不可能满足条件
        if (totol % 2 != 0) {
            return false;
        }
        //背包大小
        int target = totol / 2;
        //如果最大值大于target不可能满足条件
        if (maxNum > target) {
            return false;
        }
        //+1是因为，当装当前物品时，背包容量=当前物品，那么还剩下容量为0的背包，一定是满的
        boolean[][] dp = new boolean[nums.length][target + 1];
        //背包容量为0，可以看作背包已经满了
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        //初始化值，当只有一个物品nums[0]时，背包容量=nums[0]才能装满背包，不存在数组越界问题，因为之前已经判断过最大值是否大于target
        dp[0][nums[0]] = true;
        //从第二行开始计算，第一行只有一个物品，物品质量=容量=true
        for (int rows = 1; rows < dp.length; rows++) {
            //从第二列开始算，第一列背包容量为0，全部=true
            for (int columns = 1; columns < target + 1; columns++) {
                //如果当前物品可以装进背包，那么有两种选择，装或不装
                //rows: 物品质量  ； columns：背包容量
                if (nums[rows] <= columns) {
                    //装：rows-1=上一个物品，columns - nums[rows]=剩下的容量，是否可以装满背包
                    //不装：上一个物品是否可以装满columns容量的背包
                    //满足一个就行
                    dp[rows][columns] = dp[rows - 1][columns - nums[rows]] || dp[rows - 1][columns];
                } else {//物品质量比背包容量大，装不了，只能看当前背包容量columns是否可以上一个物品可以装满
                    dp[rows][columns] = dp[rows - 1][columns];
                }
            }
        }
        return dp[nums.length - 1][target];
    }

    //TODO 空间复杂度待优化

}
